__author__ = 'likang'

count = 0

def divideAndConquer(arrayToSort, low, high) :
    if low < high :
        mid = (low + high) / 2
        divideAndConquer(arrayToSort, low, mid)
        divideAndConquer(arrayToSort, mid + 1, high)
        merge(arrayToSort, low, mid, high)

def merge(arrayToSort, low, mid, high) :
    i = low
    j = mid + 1
    k = low
    global count
    arraynew=[0]*len(arrayToSort)
    while i <= mid and j <= high :
        if (arrayToSort[i] <= 3*arrayToSort[j]):
            k = k + 1
            i = i + 1
        else:
            k = k + 1
            j = j + 1
            count = count + j - k
    i = low
    j = mid + 1
    k = low
    while i <= mid and j <= high :
        if (arrayToSort[i] <= arrayToSort[j]):
            arraynew[k] = arrayToSort[i]
            k = k + 1
            i = i + 1
        else:
            arraynew[k] = arrayToSort[j]
            k = k + 1
            j = j + 1
    while i <= mid:
        arraynew[k] = arrayToSort[i]
        k = k + 1
        i = i + 1
    while j <= high:
        arraynew[k] = arrayToSort[j]
        k = k + 1
        j = j + 1
    for i in range(low, high+1) :
        arrayToSort[i] = arraynew[i]

if __name__ == "__main__" :
    arrayToSort = [9,2,9,2,2,2,7,2]
    divideAndConquer(arrayToSort,0,7)
    print arrayToSort
    print count